#include "twenty_four.h"
#include <stdlib.h>
#include <stdio.h>


void TF_list_insert(struct TF_List * list, int v) {
    struct TF_Node * node = (struct TF_Node *)malloc(sizeof(struct TF_Node));
    node->v = (struct TF_Item){
            v,
            __INT_MAX__,
            0,
            0,
            0,
            White,
            nullptr,
            nullptr,
            nullptr,
            __INT_MAX__,
    };
    node->next = nullptr;
    if (TF_list_is_empty(list)) {
        list->head = node;
        list->tail = node;
        node->pre = nullptr;
    } else {
        list->tail->next = node;
        node->pre = list->tail;
        list->tail = node;
    }
    list->count++;
}

int TF_list_is_empty(struct TF_List * list) {
    if (list->head == nullptr && list->tail == nullptr && list->count == 0) {
        return 1;
    } else {
        return 0;
    }
}

struct TF_Node * TF_list_find(struct TF_List * list, int v) {
    struct TF_Node * current = list->head;
    while (current != nullptr) {
        if (current->v.v == v) {
            return current;
        } else {
            current = current->next;
        }
    }
    return nullptr;
}

void TF_node_show(struct TF_Node * node) {
    if (node->v.pi == nullptr) {
        printf("%d --> NULL : %d(%d/%d)", node->v.v, node->v.d, node->v.f, node->v.e);

    } else {
        printf("%d --> %d : %d(%d/%d)", node->v.v, node->v.pi->v.v, node->v.d, node->v.f, node->v.e);
    }
    if (node->pre == nullptr) {
        printf("[NULL:");
    } else {
        printf("[%d:", node->pre->v.v);
    }
    if (node->next == nullptr) {
        printf("NULL]");
    } else {
        printf("%d]", node->next->v.v);
    }
    if (node->v.list != nullptr) {
        printf("\n");
        TF_adjacency_list_show(node->v.list);
    }
}

void TF_list_show(struct TF_List * list) {
    printf("-----------------------------\n");
    struct TF_Node * current = list->head;
    while (current != nullptr) {
        TF_node_show(current);
        printf("\n");
        current = current->next;
    }
}

int TF_adjacency_list_is_empty(struct TF_Adjacency_List * list) {
    if (list->head == nullptr && list->tail == nullptr && list->count == 0) {
        return 1;
    } else {
        return 0;
    }
}

void TF_adjacency_list_insert(struct TF_Adjacency_List * list, struct TF_Node * node, int w) {
    struct TF_Adjacency_Node * ad_node = (struct TF_Adjacency_Node *)malloc(sizeof(struct TF_Adjacency_Node));
    ad_node->v = (struct TF_Adjacency_Item){
       node,
       w
    };
    ad_node->next = nullptr;
    if (TF_adjacency_list_is_empty(list)) {
        list->head = ad_node;
        list->tail = ad_node;
    } else {
        list->tail->next = ad_node;
        list->tail = ad_node;
    }
    list->count++;
}

void TF_list_clear(struct TF_List * list) {
    struct TF_Node * current = list->head;
    struct TF_Node * free_node = nullptr;
    while (current != nullptr) {
        TF_adjacency_list_clear(current->v.list);
        free_node = current;
        current = current->next;
        free(free_node);
    }
    list->head = nullptr;
    list->tail = nullptr;
    list->count = 0;
}

void TF_adjacency_list_clear(struct TF_Adjacency_List * list) {
    struct TF_Adjacency_Node * current = list->head;
    struct TF_Adjacency_Node * free_node = nullptr;
    while (current != nullptr) {
        free_node = current;
        current = current->next;
        free(free_node);
    }
    list->head = nullptr;
    list->tail = nullptr;
    list->count = 0;
}

void TF_adjacency_node_show(struct TF_Adjacency_Node * node) {
    printf("(%d, %d)", node->v.v->v.v, node->v.w);
}

void TF_adjacency_list_show(struct TF_Adjacency_List * list) {
    struct TF_Adjacency_Node * current = list->head;
    printf("[ ");
    while (current != nullptr) {
        TF_adjacency_node_show(current);
        printf(" ");
        current = current->next;
    }
    printf(" ]");
}

void relax(struct TF_Node * u, struct TF_Node * v, int w) {
    if (v->v.d > u->v.d + w) {
        v->v.d = u->v.d + w;
        v->v.pi = u;
    }
}

int bellman_ford(struct TF_List * list, struct TF_Node * s) {
    s->v.d = 0;
    if (TF_list_is_empty(list)) {
        return 0;
    }
    int loop_count = list->count - 1;
    for (int i = 0; i < loop_count; i++) {
        struct TF_Node * u = list->head;
        while (u != nullptr) {
            struct TF_Adjacency_Node * v = u->v.list->head;
            while (v != nullptr) {
                relax(u, v->v.v, v->v.w);
                v = v->next;
            }
            u = u->next;
        }
    }

    struct TF_Node * u = list->head;
    while (u != nullptr) {
        struct TF_Adjacency_Node * v = u->v.list->head;
        while (v != nullptr) {
            if (v->v.v->v.d > u->v.d + v->v.w) {
                return 0;
            }
            v = v->next;
        }
        u = u->next;
    }

    return 1;
}

void pi_show(struct TF_List * list) {
    printf("---------------------------------\n");
    struct TF_Node * current = list->head;
    while (current != nullptr) {
        printf("%d --> ", current->v.v);
        struct TF_Node * pi = current->v.pi;
        while (pi != nullptr) {
            printf("%d --> ", pi->v.v);
            pi = pi->v.pi;
        }
        printf("NULL\n");
        current = current->next;
    }
}

void dfs(struct TF_List * list) {
    int time = 0;
    struct TF_Node * current = list->head;
    while (current != nullptr) {
        if (current->v.color == White) {
            dfs_visit(current, &time);
        }
        current = current->next;
    }
}

void dfs_visit(struct TF_Node * node, int * time) {
    (*time)++;
    node->v.f = *time;
    node->v.color = Gray;
    struct TF_Adjacency_Node * current = node->v.list->head;
    while (current != nullptr) {
        if (current->v.v->v.color == White) {
            current->v.v->v.dfs_pi = node;
            dfs_visit(current->v.v, time);
        }
        current = current->next;
    }
    node->v.color = Black;
    (*time)++;
    node->v.e = *time;
}

void topological_sort(struct TF_List * list) {
    dfs(list);
    printf("After dfs ......\n");
    TF_list_show(list);
    printf("----------------\n");
    struct TF_Node * current = list->head;
    struct TF_Node * pro_node = nullptr;
    while (current != nullptr) {
        printf("Insert Sort ......\n");
        printf("current: %d\n", current->v.v);
        pro_node = find_max_e(current);
        printf("pro_node: %d\n", pro_node->v.v);
        if (pro_node->v.v == current->v.v) {
            current = current->next;
        }
        if (pro_node->pre != nullptr) {
            pro_node->pre->next = pro_node->next;
            if (pro_node->next != nullptr) {
               pro_node->next->pre = pro_node->pre;
            } else {
                list->tail = pro_node->pre;
            }
            pro_node->pre = nullptr;
            pro_node->next = list->head;
            list->head->pre = pro_node;
            list->head = pro_node;
        }
        TF_list_show(list);
        printf("----------------\n");
    }
}

struct TF_Node * find_max_e(struct TF_Node * node) {
    struct TF_Node * res = node;
    node = node->next;
    while (node != nullptr) {
        if (node->v.e > res->v.e) {
            res = node;
        }
        node = node->next;
    }
    return(res);
}

void dag_shortest_paths(struct TF_List * list) {
    struct TF_Node * u = list->tail;
    u->v.d = 0;
    while (u->pre != nullptr) {
        struct TF_Adjacency_Node * v = u->v.list->head;
        while (v != nullptr) {
            relax(u, v->v.v, v->v.w);
            v = v->next;
        }
        u = u->pre;
    }
}

inline static int parent(int i) {
    return((i-1)/2);
}

inline static int left(int i) {
    return(2*i+1);
}
inline static int right(int i) {
    return(2*(i+1));
}

void min_heapify(struct TF_HEAP * q, int i) {
    int l = left(i);
    int r = right(i);
    int least = i;
    if (l <= q->size && q->list[l]->v.d < q->list[i]->v.d) {
        least = l;
    }
    if (r <= q->size && q->list[r]->v.d < q->list[i]->v.d) {
        least = r;
    }
    if (least != i) {
        q->list[i]->v.heap_i = least;
        q->list[least]->v.heap_i = i;
        struct TF_Node * temp = q->list[i];
        q->list[i] = q->list[least];
        q->list[least] = temp;
        min_heapify(q, least);
    }
}

void build_min_heap(struct TF_HEAP * q) {
    for (int i = parent(q->size-1); i >= 0; i--) {
        min_heapify(q, i);
    }
}

void heapsort(struct TF_HEAP * q) {
    build_min_heap(q);
    for (int i = q->size-1; i > 0; i--) {
        q->list[0]->v.heap_i = i;
        q->list[i]->v.heap_i = 0;
        struct TF_Node * temp = q->list[0];
        q->list[0] = q->list[i];
        q->list[i] = temp;
        q->size--;
        min_heapify(q, 0);
    }
}

struct TF_Node * heap_extract_min(struct TF_HEAP * q) {
    if (q->size < 1) {
        printf("heap underflow!");
        return nullptr;
    }
    struct TF_Node * min = q->list[0];
    q->list[q->size-1]->v.heap_i = 0;
    q->list[0] = q->list[q->size-1];
    q->size--;
    min_heapify(q, 0);
    return min;
}

void heap_insert(struct TF_HEAP * q, struct TF_Node * node) {
    q->size++;
    q->list[q->size-1] = node;
    node->v.heap_i = q->size-1;
    heap_decrease_key(q, q->size-1, node->v.d);
}

struct TF_Node * minmum(struct TF_HEAP * q) {
    return(q->list[0]);
}


void heap_decrease_key(struct TF_HEAP * q, int i, int k) {
    if (q->list[i]->v.d < k) {
        printf("new key is bigger than current key!\n");
        return;
    }
    q->list[i]->v.d = k;
    while (i > 0 && q->list[parent(i)]->v.d > k) {
        q->list[parent(i)]->v.heap_i = i;
        q->list[i]->v.heap_i = parent(i);
        struct TF_Node * temp = q->list[i];
        q->list[i] = q->list[parent(i)];
        q->list[parent(i)] = temp;
        i = parent(i);
    }
}

void dijkstra(struct TF_List * list) {

    list->head->v.d = 0;

    struct TF_Node * s_list[list->count];
    for (int i = 0; i < list->count; i++) {
        s_list[i] = nullptr;
    }
    struct TF_HEAP s = {s_list, 0};

    struct TF_Node * q_list[list->count];
    struct TF_Node * current = list->head;
    for (int i = 0; i < list->count; i++) {
        q_list[i] = current;
        current->v.heap_i = i;
        current = current->next;
    }
    struct TF_HEAP q = {q_list, list->count};
    build_min_heap(&q);

    struct TF_Node * u = nullptr;
    while (q.size != 0) {
        u = heap_extract_min(&q);
        heap_insert(&s, u);
        struct TF_Adjacency_Node * v = u->v.list->head;
        while (v != nullptr) {
            if (v->v.v->v.d > u->v.d + v->v.w) {
                v->v.v->v.pi = u;
                heap_decrease_key(&q, v->v.v->v.heap_i, u->v.d + v->v.w);
            }
            v = v->next;
        }
    }
}
